home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / The World of Computer Software.iso / srcuc.zip / STACK.H < prev    next >
C/C++ Source or Header  |  1992-02-03  |  14KB  |  417 lines
  1. /* -*-C-*-
  2.  
  3. $Header: /scheme/src/microcode/RCS/stack.h,v 9.30 1992/02/03 23:38:30 jinx Exp $
  4.  
  5. Copyright (c) 1987-1992 Massachusetts Institute of Technology
  6.  
  7. This material was developed by the Scheme project at the Massachusetts
  8. Institute of Technology, Department of Electrical Engineering and
  9. Computer Science.  Permission to copy this software, to redistribute
  10. it, and to use it for any purpose is granted, subject to the following
  11. restrictions and understandings.
  12.  
  13. 1. Any copy made of this software must include this copyright notice
  14. in full.
  15.  
  16. 2. Users of this software agree to make their best efforts (a) to
  17. return to the MIT Scheme project any improvements or extensions that
  18. they make, so that these may be included in future releases; and (b)
  19. to inform MIT of noteworthy uses of this software.
  20.  
  21. 3. All materials developed as a consequence of the use of this
  22. software shall duly acknowledge such use, in accordance with the usual
  23. standards of acknowledging credit in academic research.
  24.  
  25. 4. MIT has made no warrantee or representation that the operation of
  26. this software will be error-free, and MIT is under no obligation to
  27. provide any services, by way of maintenance, update, or otherwise.
  28.  
  29. 5. In conjunction with products arising from the use of this material,
  30. there shall be no use of the name of the Massachusetts Institute of
  31. Technology nor of any adaptation thereof in any advertising,
  32. promotional, or sales literature without prior written consent from
  33. MIT in each case. */
  34.  
  35. /* This file contains macros for manipulating stacks and stacklets. */
  36.  
  37. #ifdef USE_STACKLETS
  38.  
  39. /*
  40.   Stack is made up of linked small parts, each in the heap
  41.  */
  42.  
  43. #define Initialize_Stack()                        \
  44. {                                    \
  45.   if (GC_Check(Default_Stacklet_Size))                    \
  46.   {                                    \
  47.     Microcode_Termination(TERM_STACK_ALLOCATION_FAILED);        \
  48.   }                                    \
  49.   Stack_Guard = (Free + STACKLET_HEADER_SIZE);                \
  50.   *Free =                                \
  51.     (MAKE_OBJECT (TC_MANIFEST_VECTOR, (Default_Stacklet_Size - 1)));    \
  52.   Free += Default_Stacklet_Size;                    \
  53.   Stack_Pointer = Free;                            \
  54.   Free_Stacklets = NULL;                        \
  55.   Prev_Restore_History_Stacklet = NULL;                    \
  56.   Prev_Restore_History_Offset = 0;                    \
  57. }
  58.  
  59. #define Internal_Will_Push(N)                        \
  60. {                                    \
  61.   if ((Stack_Pointer - (N)) < Stack_Guard)                \
  62.   {                                    \
  63.     Export_Registers();                            \
  64.     Allocate_New_Stacklet((N));                        \
  65.     Import_Registers();                            \
  66.   }                                    \
  67. }
  68.  
  69. /* No space required independent of the heap for the stacklets */
  70.  
  71. #define Stack_Allocation_Size(Stack_Blocks)    0
  72.  
  73. #define Current_Stacklet    (Stack_Guard - STACKLET_HEADER_SIZE)
  74.  
  75. /* Make the unused portion of the old stacklet invisible to garbage
  76.  * collection. This also allows the stack pointer to be reconstructed.
  77.  */
  78.  
  79. #define Internal_Terminate_Old_Stacklet()                \
  80. {                                    \
  81.   Current_Stacklet[STACKLET_REUSE_FLAG] = SHARP_T;            \
  82.   Current_Stacklet[STACKLET_UNUSED_LENGTH] =                \
  83.     MAKE_OBJECT (TC_MANIFEST_NM_VECTOR, (Stack_Pointer - Stack_Guard));    \
  84. }
  85.  
  86. #ifdef ENABLE_DEBUGGING_TOOLS
  87.  
  88. #define Terminate_Old_Stacklet()                    \
  89. {                                    \
  90.   if (Stack_Pointer < Stack_Guard)                    \
  91.   {                                    \
  92.     fprintf(stderr, "\nStack_Pointer: 0x%lx, Guard: 0x%lx\n",        \
  93.             ((long) Stack_Pointer), ((long) Stack_Guard));        \
  94.     Microcode_Termination(TERM_EXIT);                    \
  95.   }                                    \
  96.   Internal_Terminate_Old_Stacklet();                    \
  97. }
  98.  
  99. #else
  100.  
  101. #define Terminate_Old_Stacklet()    Internal_Terminate_Old_Stacklet()
  102.  
  103. #endif
  104.  
  105. /* Used by garbage collector to detect the end of constant space */
  106.  
  107. #define CONSTANT_SCAN_SEAL()  Free_Constant
  108.  
  109. #define SEAL_CONSTANT_SPACE()                        \
  110.   *Free_Constant =                            \
  111.     (MAKE_POINTER_OBJECT (TC_BROKEN_HEART, Free_Constant));
  112.  
  113. #define CONSTANT_SPACE_SEALED()                        \
  114. ((*Free_Constant) == (MAKE_POINTER_OBJECT (TC_BROKEN_HEART, Free_Constant)))
  115.  
  116. #define Get_Current_Stacklet()                        \
  117.   (MAKE_POINTER_OBJECT (TC_CONTROL_POINT, Current_Stacklet))
  118.  
  119. #define Previous_Stack_Pointer(Where)                    \
  120.   (MEMORY_LOC                                \
  121.    (Where,                                \
  122.     (STACKLET_HEADER_SIZE +                        \
  123.      (OBJECT_DATUM (MEMORY_REF (Where, STACKLET_UNUSED_LENGTH))))))
  124.  
  125. #define Set_Current_Stacklet(Where)                    \
  126. {                                    \
  127.   SCHEME_OBJECT Our_Where;                        \
  128.                                     \
  129.   Our_Where = (Where);                            \
  130.   Stack_Guard = MEMORY_LOC (Our_Where, STACKLET_HEADER_SIZE);        \
  131.   Stack_Pointer = Previous_Stack_Pointer(Our_Where);            \
  132. }
  133.  
  134. #define STACKLET_SLACK    (STACKLET_HEADER_SIZE + CONTINUATION_SIZE)
  135.  
  136. #define Default_Stacklet_Size     (Stack_Size + STACKLET_SLACK)
  137.  
  138. #define New_Stacklet_Size(N)                        \
  139.  (STACKLET_SLACK + Stack_Size * (((N) + Stack_Size - 1) / Stack_Size))
  140.  
  141. #define Get_End_Of_Stacklet()                        \
  142.   (&(Current_Stacklet[1 + OBJECT_DATUM (Current_Stacklet[STACKLET_LENGTH])]))
  143.  
  144. #define Apply_Stacklet_Backout()                    \
  145. Will_Push((2 * CONTINUATION_SIZE) + (STACK_ENV_EXTRA_SLOTS + 2));    \
  146.   Store_Expression(SHARP_F);                        \
  147.   Store_Return(RC_END_OF_COMPUTATION);                    \
  148.   Save_Cont();                                \
  149.   STACK_PUSH (Val);                            \
  150.   STACK_PUSH (Previous_Stacklet);                    \
  151.   STACK_PUSH (STACK_FRAME_HEADER + 1);                    \
  152.   Store_Return(RC_INTERNAL_APPLY);                    \
  153.   Save_Cont();                                \
  154. Pushed()
  155.  
  156. #define Join_Stacklet_Backout()        Apply_Stacklet_Backout()
  157.  
  158. /* This depends on the fact that Within_Control_Point is going to
  159.  * push an apply frame immediately after Return_To_Previous_Stacklet
  160.  * "returns".  This apply will cause the GC, then the 2nd argument to
  161.  * Within_Control_Point will be invoked, and finally the control point
  162.  * will be entered.
  163.  */
  164.  
  165. #define Within_Stacklet_Backout()                    \
  166. {                                    \
  167.   SCHEME_OBJECT Old_Expression;                        \
  168.                                     \
  169.   Old_Expression = Fetch_Expression();                    \
  170.   Store_Expression(Previous_Stacklet);                    \
  171.   Store_Return(RC_JOIN_STACKLETS);                    \
  172.   Save_Cont();                                \
  173.   Store_Expression(Old_Expression);                    \
  174. }
  175.  
  176. /* Our_Throw is used in chaining from one stacklet to another.  In
  177.  * order to improve efficiency, the entire stack is copied neither on
  178.  * catch or throw, but is instead copied one stacklet at a time as
  179.  * needed.  The need to copy a stacklet is signified by the object in
  180.  * the STACKLET_REUSE_FLAG of a stacklet.  If this object is #F, the
  181.  * stacklet is copied when it is "returned into", and the word is set
  182.  * to #F in the stacklet into which the copied one will return. When a
  183.  * stacklet is returned from, it is no longer needed for anything so it
  184.  * can be deallocated.  A free list of deallocate stacklets is kept in
  185.  * order to improve the efficiencty of their use.
  186.  */
  187.  
  188. #define Our_Throw(From_Pop_Return, Stacklet)                \
  189. {                                    \
  190.   SCHEME_OBJECT Previous_Stacklet;                    \
  191.   SCHEME_OBJECT *Stacklet_Top;                        \
  192.                                     \
  193.   Previous_Stacklet = (Stacklet);                    \
  194.   Stacklet_Top = Current_Stacklet;                    \
  195.   Stacklet_Top[STACKLET_FREE_LIST_LINK] =                \
  196.     ((SCHEME_OBJECT) Free_Stacklets);                    \
  197.   Free_Stacklets = Stacklet_Top;                    \
  198.   if (!(From_Pop_Return))                        \
  199.   {                                    \
  200.     Prev_Restore_History_Stacklet = NULL;                \
  201.     Prev_Restore_History_Offset = 0;                    \
  202.   }                                    \
  203.   if ((MEMORY_REF (Previous_Stacklet, STACKLET_REUSE_FLAG)) == SHARP_F)    \
  204.   {                                    \
  205.     /* We need to copy the stacklet into which we are            \
  206.        returning.                            \
  207.      */                                    \
  208.                                     \
  209.     if (GC_Check(VECTOR_LENGTH (Previous_Stacklet) + 1))        \
  210.     {                                    \
  211.       /* We don't have enough space to copy the stacklet. */        \
  212.                                     \
  213.       Free_Stacklets =                            \
  214.     ((SCHEME_OBJECT *) Free_Stacklets[STACKLET_FREE_LIST_LINK]);    \
  215.       Stack_Pointer = Get_End_Of_Stacklet();                \
  216.       Prev_Restore_History_Stacklet = NULL;                \
  217.       Prev_Restore_History_Offset = 0
  218.  
  219.       /* Backout code inserted here by macro user */
  220.  
  221. #define Our_Throw_Part_2()                        \
  222.       Request_GC(VECTOR_LENGTH (Previous_Stacklet) + 1);        \
  223.     }                                    \
  224.     else                                \
  225.     {                                    \
  226.       /* There is space available to copy the stacklet. */        \
  227.                                     \
  228.       long Unused_Length;                        \
  229.       fast Used_Length;                            \
  230.       fast SCHEME_OBJECT *Old_Stacklet_Top, *temp;            \
  231.       SCHEME_OBJECT *First_Continuation;                \
  232.                                     \
  233.       Old_Stacklet_Top = OBJECT_ADDRESS (Previous_Stacklet);        \
  234.       First_Continuation =                        \
  235.         MEMORY_LOC (Previous_Stacklet,                    \
  236.             ((1 + VECTOR_LENGTH (Previous_Stacklet)) -        \
  237.              CONTINUATION_SIZE));                \
  238.       if (Old_Stacklet_Top == Prev_Restore_History_Stacklet)        \
  239.       {                                    \
  240.         Prev_Restore_History_Stacklet = NULL;                \
  241.       }                                    \
  242.       if (First_Continuation[CONTINUATION_RETURN_CODE] ==        \
  243.       MAKE_OBJECT (TC_RETURN_CODE, RC_JOIN_STACKLETS))        \
  244.       {                                    \
  245.     SCHEME_OBJECT Older_Stacklet;                    \
  246.                                     \
  247.     Older_Stacklet = First_Continuation[CONTINUATION_EXPRESSION];    \
  248.     MEMORY_SET (Older_Stacklet, STACKLET_REUSE_FLAG, SHARP_F);    \
  249.       }                                    \
  250.       temp = Free;                            \
  251.       Stack_Guard = &(temp[STACKLET_HEADER_SIZE]);            \
  252.       temp[STACKLET_LENGTH] = Old_Stacklet_Top[STACKLET_LENGTH];    \
  253.       Unused_Length =                            \
  254.     OBJECT_DATUM (Old_Stacklet_Top[STACKLET_UNUSED_LENGTH]) +    \
  255.         STACKLET_HEADER_SIZE;                        \
  256.       temp += Unused_Length;                        \
  257.       Stack_Pointer = temp;                        \
  258.       Used_Length =                            \
  259.         (OBJECT_DATUM (Old_Stacklet_Top[STACKLET_LENGTH]) -        \
  260.          Unused_Length) + 1;                        \
  261.       Old_Stacklet_Top += Unused_Length;                \
  262.       while (--Used_Length >= 0)                    \
  263.       {                                    \
  264.     *temp++ = *Old_Stacklet_Top++;                    \
  265.       }                                    \
  266.       Free = temp;                            \
  267.     }                                    \
  268.   }                                    \
  269.   else                                    \
  270.   {                                    \
  271.     /* No need to copy the stacklet we are going into */        \
  272.                                     \
  273.     if (OBJECT_ADDRESS (Previous_Stacklet)==                \
  274.         Prev_Restore_History_Stacklet)                    \
  275.     {                                    \
  276.       Prev_Restore_History_Stacklet = NULL;                \
  277.     }                                    \
  278.     Set_Current_Stacklet(Previous_Stacklet);                \
  279.   }                                    \
  280. }
  281.  
  282. #else /* not USE_STACKLETS */
  283.  
  284. /*
  285.   Full size stack in a statically allocated area
  286.  */
  287.  
  288. #define Stack_Check(P)                            \
  289. do                                    \
  290. {                                    \
  291.   if ((P) <= Stack_Guard)                        \
  292.     {                                    \
  293.       if ((P) <= Absolute_Stack_Base)                    \
  294.       {                                    \
  295.     Microcode_Termination (TERM_STACK_OVERFLOW);            \
  296.       }                                    \
  297.       REQUEST_INTERRUPT (INT_Stack_Overflow);                \
  298.     }                                    \
  299. } while (0)
  300.  
  301. #define Internal_Will_Push(N)    Stack_Check(Stack_Pointer - (N))
  302.  
  303. #define Stack_Allocation_Size(Stack_Blocks) (Stack_Blocks)
  304.  
  305. #define Terminate_Old_Stacklet()
  306.  
  307. /* Used by garbage collector to detect the end of constant space, and to
  308.    skip over the gap between constant space and the stack. */
  309.  
  310. #define CONSTANT_SPACE_SEAL()  Stack_Top
  311.  
  312. #define SEAL_CONSTANT_SPACE()                        \
  313. do                                    \
  314. {                                    \
  315.   *Free_Constant =                            \
  316.     (MAKE_OBJECT                            \
  317.      (TC_MANIFEST_NM_VECTOR, ((Stack_Pointer - Free_Constant) - 1)));    \
  318.   *(Free_Constant + 1) =                        \
  319.     (MAKE_POINTER_OBJECT (TC_BROKEN_HEART, (Free_Constant + 1)));    \
  320.   *Stack_Top = (MAKE_POINTER_OBJECT (TC_BROKEN_HEART, Stack_Top));    \
  321. } while (0)
  322.  
  323. #define CONSTANT_SPACE_SEALED()                        \
  324. ((*(Free_Constant + 1)) ==                        \
  325.  (MAKE_POINTER_OBJECT (TC_BROKEN_HEART, (Free_Constant + 1))))
  326.  
  327. #define Get_Current_Stacklet() SHARP_F
  328.  
  329. #define Set_Current_Stacklet(Where) {}
  330.  
  331. #define Previous_Stack_Pointer(Where)                    \
  332.   (MEMORY_LOC                                \
  333.    (Where,                                \
  334.     (STACKLET_HEADER_SIZE +                        \
  335.      (OBJECT_DATUM (MEMORY_REF (Where, STACKLET_UNUSED_LENGTH))))))
  336.  
  337. /* Never allocate more space */
  338. #define New_Stacklet_Size(N)    0
  339.  
  340. #define Get_End_Of_Stacklet()    Stack_Top
  341.  
  342. /* Not needed in this version */
  343.  
  344. #define Join_Stacklet_Backout()
  345. #define Apply_Stacklet_Backout()
  346. #define Within_Stacklet_Backout()
  347.  
  348. /* This piece of code KNOWS which way the stack grows.
  349.    The assumption is that successive pushes modify decreasing addresses.
  350.  */
  351.  
  352. /* Clear the stack and replace it with a copy of the contents of the
  353.    control point. Also disables the history collection mechanism,
  354.    since the saved history would be incorrect on the new stack. */
  355.  
  356. #define Our_Throw(From_Pop_Return, P)                    \
  357. {                                    \
  358.   SCHEME_OBJECT Control_Point;                        \
  359.   fast SCHEME_OBJECT *To_Where, *From_Where;                \
  360.   fast long len, valid, invalid;                    \
  361.                                     \
  362.   Control_Point = (P);                            \
  363.   if (Consistency_Check)                        \
  364.   {                                    \
  365.     if (OBJECT_TYPE (Control_Point) != TC_CONTROL_POINT)        \
  366.     {                                    \
  367.       Microcode_Termination (TERM_BAD_STACK);                \
  368.     }                                    \
  369.   }                                    \
  370.   len = VECTOR_LENGTH (Control_Point);                    \
  371.   invalid = ((OBJECT_DATUM (MEMORY_REF (Control_Point,            \
  372.                     STACKLET_UNUSED_LENGTH))) +    \
  373.          STACKLET_HEADER_SIZE);                    \
  374.   valid = ((len + 1) - invalid);                    \
  375.   CLEAR_INTERRUPT(INT_Stack_Overflow);                    \
  376.   To_Where = (Stack_Top - valid);                    \
  377.   From_Where = MEMORY_LOC (Control_Point, invalid);            \
  378.   Stack_Check (To_Where);                        \
  379.   Stack_Pointer = To_Where;                        \
  380.   while (--valid >= 0)                            \
  381.   {                                    \
  382.     *To_Where++ = *From_Where++;                    \
  383.   }                                    \
  384.   if (Consistency_Check)                        \
  385.   {                                    \
  386.     if ((To_Where != Stack_Top) ||                    \
  387.     (From_Where !=                            \
  388.      MEMORY_LOC (Control_Point, (1 + len))))            \
  389.     {                                    \
  390.       Microcode_Termination (TERM_BAD_STACK);                \
  391.     }                                    \
  392.   }                                    \
  393.   if (!(From_Pop_Return))                        \
  394.   {                                    \
  395.     Prev_Restore_History_Stacklet = NULL;                \
  396.     Prev_Restore_History_Offset = 0;                    \
  397.     if ((!Valid_Fixed_Obj_Vector ()) ||                    \
  398.     (Get_Fixed_Obj_Slot (Dummy_History) == SHARP_F))        \
  399.     {                                    \
  400.       History = Make_Dummy_History ();                    \
  401.     }                                    \
  402.     else                                \
  403.     {                                    \
  404.       History = OBJECT_ADDRESS (Get_Fixed_Obj_Slot (Dummy_History));    \
  405.     }                                    \
  406.   }                                    \
  407.   else if (Prev_Restore_History_Stacklet ==                \
  408.        OBJECT_ADDRESS (Control_Point))                \
  409.   {                                    \
  410.     Prev_Restore_History_Stacklet = NULL;                \
  411.   }                                    \
  412. }
  413.  
  414. #define Our_Throw_Part_2()
  415.  
  416. #endif /* USE_STACKLETS */
  417.